package LeetCode;

import java.util.Arrays;

/**
 * @Classname LC494
 * @Description // https://leetcode-cn.com/problems/target-sum/  动态规划  回溯
 * @Date 2021/4/20 21:03
 * @Created by yin
 */
public class LC494 {
    private int ans;

    public int findTargetSumWays(int[] nums, int target) {
        backtrace(nums, 0, target);
        return ans;
    }

    // 回溯法
    public void backtrace(int[] nums, int i, int target) {
        if (i == nums.length) {
            if (target == 0) {
                ans++;
            }
            return;
        }
        // 选择+
        backtrace(nums, i + 1, target - nums[i]);
        // 选择-
        backtrace(nums, i + 1, target + nums[i]);
    }

    // 动态规划
    public int findTargetSumWays2(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if ((sum + target) % 2 == 1) return 0;
        int aim = (sum + target) / 2;
        // dp[j] 表示能不能凑成和为j的组合的个数
        int[] dp = new int[aim + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = aim; j >= 0; j--) {
                if (j - num >= 0) {
                    dp[j] = dp[j] + dp[j - num];
                }
            }
        }
        return dp[aim];
    }
}
